package PrefixSum;

import java.util.HashMap;

//https://leetcode.cn/problems/contiguous-array/
public class l_525 {
    public int findMaxLength(int[] nums) {
        //将0转换为-1, 就是求存在负数的和为0的最长子数组, 前缀和加哈希表即可
        int n = nums.length, ans = 0;
        for(int i = 0; i < n; i++) nums[i] = nums[i] == 0 ? -1 : 1;
        //哈希表存的是前缀和, 前缀和的末尾下标
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1); //存在sum为0的情况, 这里-1很关键, 少了一些特判
        for(int i = 0, sum = 0; i < n; i++)
        {
            sum += nums[i];
            if(hash.containsKey(sum))
                ans = Math.max(ans, i - hash.get(sum));
            else
                hash.put(sum, i); //不存在才将这个前缀和及其末尾下标存入, 如果存在相同的前缀和肯定是保留之前存在的更优
        }
        return ans;
    }
}
